package com.rongji.dfish.base.tree;


import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.*;

/**
 * 树节点
 * 一般拿某个树的顶级节点当做树的句柄
 * @param <E> 数据类型
 */
public class TreeNode<E> {
    private E data;
    private String id;
    private TreeNode<E> parent;
    private List<TreeNode<E>> children;
    private int level;

    /**
     * 树的数据
     * @return E data
     */
    public E getData() {
        return data;
    }

    /**
     * 树的数据
     * @param data E
     */
    public void setData(E data) {
        this.data = data;
    }

    /**
     * 编号
     * @return String
     */
    public String getId() {
        return id;
    }

    /**
     * 编号
     * @param id String
     */
    public void setId(String id) {
        this.id = id;
    }

    /**
     * 不用getter写法。不希望JSON 输出该字段
     * @return TreeNode
     */
    public TreeNode<E> parent() {
        return parent;
    }

    /**
     * 设置父节点
     * @param parent TreeNode
     */
    public void parent(TreeNode<E> parent) {
        this.parent = parent;
    }

    /**
     * 子节点列表
     * @return List
     */
    public List<TreeNode<E>> getChildren() {
        return children;
    }

    /**
     * 子节点列表
     * @param children List
     */
    public void setChildren(List<TreeNode<E>> children) {
        this.children = children;
    }

    /**
     * 层级
     * @return int
     */
    public int getLevel() {
        return level;
    }

    /**
     * 层级
     * @param level int
     */
    public void setLevel(int level) {
        this.level = level;
    }

    /**
     * 删除树节点下指定的节点
     * 不会删除自己。
     *
     * @param p Predicate 条件
     */
    public void remove(Predicate<TreeNode<E>> p) {
        if (p == null) {
            return;
        }
        if (children != null) {
            for (Iterator<TreeNode<E>> iter = children.iterator(); iter.hasNext(); ) {
                TreeNode<E> n = iter.next();
                if (p.test(n)) {
                    iter.remove();
                }
                n.parent(null);
                n.remove(p);
                AtomicInteger idGen=new AtomicInteger(ID_INDEX_START);
                n.forEach(node->{
                    node.setLevel(node.parent==null?0:node.parent.level+1);
                    node.setId(Integer.toHexString(idGen.getAndIncrement()).toUpperCase());
                });
            }
            if(children.size()==0){
                children=null;
            }
        }
    }


    /**
     * 增加一个节点
     *
     * @param node TreeNode
     */
    public void addChild(TreeNode<E> node) {
        if (node == null) {
            return;
        }
        if (children == null) {
            children = new ArrayList<>();
        }
        children.add(node);
        node.parent = this;
        node.level = this.level + 1;
    }

    /**
     * 复制一份完整的树，这棵树的节点操作将不会影响原树。
     * 这里的节点操作仅限定在树操作上。item里面的内容如果改变，还是会影响到原树。
     * 克隆的对象不再有parent会自动断开关联。层级也会变成0级。
     *
     * @return 克隆的对象。
     */
    @Override
    public TreeNode<E> clone() {
        return clone(null, 0);
    }

    private TreeNode<E> clone(TreeNode<E> parent, int level) {
        TreeNode<E> cloned = new TreeNode<>();
        cloned.setId(id);
        cloned.setData(data);
        cloned.setLevel(level);
        cloned.parent(parent);
        if (children != null) {
            List<TreeNode<E>> children = new ArrayList<>(this.children.size());
            cloned.setChildren(children);
            for (TreeNode<E> n : this.children) {
                children.add(n.clone(cloned, level + 1));
            }
        }
        return cloned;
    }

    /**
     * 根据数据之间关系来构建树形
     * <pre>
     *     TreeNode<MenuData> treeNode=TreeNode.build(dataList,
     *                 (parent,child)->parent.getId().equals(child.getParent()));
     * </pre>
     * @param dataList 数据列表
     * @param isParent 两数据之间的关系 BiPredicate
     * @param <E> data类型
     * @return TreeNode 构建完的结果
     */
    public static <E> TreeNode<E> build(List<E> dataList, BiPredicate<E,E> isParent){
        List<TreeNode<E>> temp=new ArrayList<>(dataList.size());
        for(E data:dataList){
            TreeNode<E> node=new TreeNode<>();
            node.setData(data);
            temp.add(node);
        }
        for(TreeNode<E> parent:temp){
            for(TreeNode<E> child:temp){
                if(parent==child){
                    continue;
                }
                if(isParent.test(parent.getData(),child.getData())){
                    if(child.parent()==null) {
                        parent.addChild(child);
                    }else{
                        throw new IllegalArgumentException("isParent(BiPredicate) | data "+child.getData()+" has multiple parent.");
                    }
                }
            }
        }
        TreeNode<E> ret=new TreeNode<>();
        for(TreeNode<E> node:temp){
            if(node.parent()==null){
                ret.addChild(node);
            }
        }

        final AtomicInteger idGen=new AtomicInteger(ID_INDEX_START);
        ret.forEach((node)->{
            node.setLevel(node.parent==null?0:node.parent.level+1);
            node.setId(Integer.toHexString(idGen.getAndIncrement()).toUpperCase());
        });
        return  ret;
    }


    /**
     * 根据数据之间关系来构建树形
     * <pre>
     *     TreeNode<MenuData> treeNode=TreeNode.build(dataList, MenuData::getId, MenuData::getParent);
     * </pre>
     * @param dataList 数据列表
     * @param getChildKey 取得数据项KEY
     * @param getParentKey 取得数据项 父KEY 如果父KEY 不被所有的childKey包含，那么它将成为顶级(level=1)节点。
     * @param <E> data类型
     * @param <K> key类型
     * @return TreeNode
     */
    public static <E,K> TreeNode<E> build(List<E> dataList, Function<E,K> getChildKey, Function<E,K> getParentKey){
        HashMap<K,List<E>> children=new HashMap<>();
        HashSet<K> childKeySet=new HashSet<>();
        for(E data:dataList){
            children.computeIfAbsent(getParentKey.apply(data), key->new ArrayList<>()).add(data);
            childKeySet.add(getChildKey.apply(data));
        }
        TreeNode<E> ret=new TreeNode<>();
        ret.setLevel(0);
        for(E data:dataList){
            K k=getParentKey.apply(data);
            if(!childKeySet.contains(k)){
                //可以当做根节点
                ret.appendTo(data,children,getChildKey);
            }
        }
        final AtomicInteger idGen=new AtomicInteger(ID_INDEX_START);
        ret.forEach((node)->{
            node.setId(Integer.toHexString(idGen.getAndIncrement()).toUpperCase());
        });
        return  ret;
    }

    private <K> void appendTo(E data, Map<K,List<E>> childrenMap,Function<E,K> getChildKey) {
        TreeNode<E> node=new TreeNode<>();
        node.setData(data);
        node.parent(this);
        this.addChild(node);
        K key=getChildKey.apply(data);
        List<E> children=childrenMap.get(key);
        if(children!=null){
            for(E child:children){
                node.appendTo(child,childrenMap,getChildKey);
            }
        }
    }


    /**
     * 默认开始的编号
     */
    private static final int ID_INDEX_START = 0x1000;

    /**
     * 广度偶先遍历
     * @param action 遍历动作
     */
    public void forEach(Consumer<TreeNode<E>> action){
        action.accept(this);
        if(children!=null){
            for(TreeNode<E> child:children){
                child.forEach(action);
            }
        }
    }


//    /**
//     * 搜索节点。
//     * <pre>
//     *     Search<MenuData> s2= TreeNode.searchOf(treeNode)
//     *                 .find(n-> n.getData().getName().contains("人员管理"))
//     *                 .closest(n-> n.getData().getId().endsWith("0000"));
//     * </pre>
//     * @param node 根节点
//     * @param <E> data类型
//     * @return Search
//     */
//    public static<E> Search<E> searchOf(TreeNode<E> node) {
//        return new Search<>(node);
//    }

    /**
     * 转成search对象
     * 同 TreeNode.searchOf(this);
     * @return Search
     */
    public Search<E> search() {
        return new Search<>(this);
    }

    @Override
    public String toString(){
        return toDebugString();
    }

    /**
     * 显示成层级结构，以便调试。
     * @return String
     */
    public String toDebugString(){
        StringBuilder sb=new StringBuilder();
        toDebugString(new char[0],sb);
        return sb.toString();
    }

    private static final char CHAR_BLANK = '\u3000';//全角空格
    private static final char CHAR_I = '\u2502';//制表符 │
    private static final char CHAR_T = '\u251C';//制表符├
    private static final char CHAR_L = '\u2514';//制表符└

    private void toDebugString(char[] prefix, StringBuilder sb) {
        sb.append(prefix)
                .append("id=").append(id)
                .append(", lv=").append(level)
                .append(", data=").append(data)
                .append("\r\n");
        if(getChildren()!=null) {
            char[] newPrefix = new char[prefix.length+1];
            if (prefix.length > 1) {
                System.arraycopy(prefix,0,newPrefix,0,prefix.length-1);
            }
            if (prefix.length > 0) {
                char lastChar = prefix[prefix.length - 1];
                newPrefix[prefix.length - 1]= lastChar == CHAR_L ? CHAR_BLANK : CHAR_I;
            }
            int i = 0;
            int size=getChildren().size();
            for (TreeNode<?> child : getChildren()) {
                newPrefix[prefix.length]=++i<size? CHAR_T : CHAR_L;
                child.toDebugString(newPrefix,sb);
            }
        }
    }
}
